{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if Word Can Be Placed In Crossword"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #enumeration #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #枚举 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: placeWordInCrossword"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断单词是否能放入填字游戏内"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的矩阵&nbsp;<code>board</code>&nbsp;，它代表一个填字游戏&nbsp;<strong>当前</strong>&nbsp;的状态。填字游戏格子中包含小写英文字母（已填入的单词），表示&nbsp;<strong>空</strong>&nbsp;格的&nbsp;<code>' '</code>&nbsp;和表示&nbsp;<strong>障碍</strong>&nbsp;格子的&nbsp;<code>'#'</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果满足以下条件，那么我们可以 <strong>水平</strong>&nbsp;（从左到右 <strong>或者</strong>&nbsp;从右到左）或 <strong>竖直</strong>&nbsp;（从上到下 <strong>或者</strong>&nbsp;从下到上）填入一个单词：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>该单词不占据任何&nbsp;<code>'#'</code>&nbsp;对应的格子。</li>\n",
    "\t<li>每个字母对应的格子要么是&nbsp;<code>' '</code>&nbsp;（空格）要么与 <code>board</code>&nbsp;中已有字母 <strong>匹配</strong>&nbsp;。</li>\n",
    "\t<li>如果单词是 <strong>水平</strong>&nbsp;放置的，那么该单词左边和右边 <strong>相邻</strong>&nbsp;格子不能为&nbsp;<code>' '</code>&nbsp;或小写英文字母。</li>\n",
    "\t<li>如果单词是&nbsp;<strong>竖直</strong>&nbsp;放置的，那么该单词上边和下边&nbsp;<strong>相邻</strong><strong>&nbsp;</strong>格子不能为&nbsp;<code>' '</code>&nbsp;或小写英文字母。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串&nbsp;<code>word</code>&nbsp;，如果&nbsp;<code>word</code>&nbsp;可以被放入&nbsp;<code>board</code>&nbsp;中，请你返回&nbsp;<code>true</code>&nbsp;，否则请返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/18/crossword-1.png\" style=\"width: 170px; height: 150px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>board = [[\"#\", \" \", \"#\"], [\" \", \" \", \"#\"], [\"#\", \"c\", \" \"]], word = \"abc\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>单词 \"abc\" 可以如上图放置（从上往下）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/18/c2.png\" style=\"width: 170px; height: 151px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>board = [[\" \", \"#\", \"a\"], [\" \", \"#\", \"c\"], [\" \", \"#\", \"a\"]], word = \"ac\"\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>无法放置单词，因为放置该单词后上方或者下方相邻格会有空格。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/18/crossword-2.png\" style=\"width: 171px; height: 146px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>board = [[\"#\", \" \", \"#\"], [\" \", \" \", \"#\"], [\"#\", \" \", \"c\"]], word = \"ca\"\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>单词 \"ca\" 可以如上图放置（从右到左）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == board.length</code></li>\n",
    "\t<li><code>n == board[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>board[i][j]</code>&nbsp;可能为&nbsp;<code>' '</code>&nbsp;，<code>'#'</code>&nbsp;或者一个小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= word.length &lt;= max(m, n)</code></li>\n",
    "\t<li><code>word</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-word-can-be-placed-in-crossword](https://leetcode.cn/problems/check-if-word-can-be-placed-in-crossword/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-word-can-be-placed-in-crossword](https://leetcode.cn/problems/check-if-word-can-be-placed-in-crossword/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"#\",\" \",\"#\"],[\" \",\" \",\"#\"],[\"#\",\"c\",\" \"]]\\n\"abc\"', '[[\" \",\"#\",\"a\"],[\" \",\"#\", \"c\"],[\" \",\"#\",\"a\"]]\\n\"ac\"', '[[\"#\",\" \",\"#\"],[\" \",\" \",\"#\"],[\"#\",\" \",\"c\"]]\\n\"ca\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        def check(s: str) -> bool:\n",
    "            for i in range(len(word)):\n",
    "                if s[i] == ' ':\n",
    "                    continue\n",
    "                else:\n",
    "                    if s[i] != word[i]:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        Row = len(board)\n",
    "        Col = len(board[0])\n",
    "\n",
    "        # 先按行\n",
    "        for r in range(Row):\n",
    "            c = 0\n",
    "            while c < Col:\n",
    "                if board[r][c] == '#':\n",
    "                    c += 1\n",
    "                elif board[r][c].isalpha() or board[r][c] == ' ':\n",
    "                    s = ''\n",
    "                    cur = 0\n",
    "                    while c < Col and (board[r][c].isalpha() or board[r][c] == ' '):\n",
    "                        s += board[r][c]\n",
    "                        cur += 1\n",
    "                        c += 1\n",
    "                    if cur == len(word):\n",
    "                        if check(s) or check(s[::-1]):\n",
    "                            return True\n",
    "                    c += 1\n",
    "        # 再按列\n",
    "        for c in range(Col):\n",
    "            r = 0\n",
    "            while r < Row:\n",
    "                if board[r][c] == '#':\n",
    "                    r += 1\n",
    "                elif board[r][c].isalpha() or board[r][c] == ' ':\n",
    "                    s = ''\n",
    "                    cur = 0\n",
    "                    while r < Row and (board[r][c].isalpha() or board[r][c] == ' '):\n",
    "                        s += board[r][c]\n",
    "                        cur += 1\n",
    "                        r += 1\n",
    "                    if cur == len(word):\n",
    "                        if check(s) or check(s[::-1]):\n",
    "                            return True\n",
    "                    r += 1\n",
    "                            \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        word_length = len(word)\n",
    "        # 1. 所有长度为l的连续\" \"+相邻\"#\" 水平+垂直\n",
    "        # 2. 无视英文字母，将它视为\" \"先提取出来，最后再统一判断\n",
    "        #    对比英文字母的位置和正反序word的位置，相同则ok，不相同则false\n",
    "        '''\n",
    "        将每一行每一列都拆成\"#\"区分的子串写法\n",
    "        '''\n",
    "\n",
    "        check = []\n",
    "        for line in chain(board, zip(*board)):\n",
    "            tmp = \"\".join(line).split(\"#\")\n",
    "            for each in tmp:\n",
    "                if len(each) == word_length:\n",
    "                    check.append(each)\n",
    "                    check.append(each[::-1])\n",
    "        \n",
    "        def macth(word, check_list):\n",
    "            n = len(word)\n",
    "            for each in check_list:\n",
    "                if each == \" \" * n:\n",
    "                    return True\n",
    "                else:\n",
    "                    for i in range(n):\n",
    "                        if each[i] != word[i] and each[i] != \" \":\n",
    "                            break\n",
    "                        if i == n - 1:\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        return macth(word, check)\n",
    "    \n",
    "    # match = lambda x, y: all(a in [' ', b] for a, b in zip(x, y))\n",
    "    # for row in chain(board, zip(*board)):\n",
    "    #     for ss in ''.join(row).split('#'):\n",
    "    #         if len(ss) == len(word) and (match(ss, word) or match(ss, word[::-1])):\n",
    "    #             return True\n",
    "    # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        m, n, k = len(board), len(board[0]), len(word)\n",
    "        if n >= k:\n",
    "            for i in range(m):\n",
    "                stark, last = [], 0\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == \"#\":\n",
    "                        if j - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)):\n",
    "                            print(\"?\")\n",
    "                            return True\n",
    "                        last, stark = j + 1, []\n",
    "                    elif board[i][j] != \" \":\n",
    "                        stark.append([j, board[i][j]])\n",
    "                if n - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)):\n",
    "                    \n",
    "                    return True\n",
    "        if m >= k:\n",
    "            for j in range(n):\n",
    "                stark, last = [], 0\n",
    "                for i in range(m):\n",
    "                    if board[i][j] == \"#\":\n",
    "                        if i - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)):                            \n",
    "                            return True\n",
    "                        last, stark = i + 1, []\n",
    "                    elif board[i][j] != \" \":\n",
    "                        stark.append([i, board[i][j]])\n",
    "                if m - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)):\n",
    "\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        # find space with length equal to word\n",
    "        m, n = len(board), len(board[0])\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == '#':  continue\n",
    "                for d in range(4):\n",
    "                    # check cell before starting cell \n",
    "                    ci, cj = i - dirs[d][0], j - dirs[d][1]\n",
    "                    if 0 <= ci < m and 0 <= cj < n and board[ci][cj] != '#': continue\n",
    "\n",
    "                    ci, cj = i, j\n",
    "                    for k in range(len(word)):\n",
    "                        if not 0 <= ci < m or not 0 <= cj < n or not (board[ci][cj] == word[k] or board[ci][cj] == ' '):\n",
    "                            break\n",
    "                        ci, cj = ci + dirs[d][0], cj + dirs[d][1]\n",
    "\n",
    "                    # check cell after ending cell \n",
    "                    else:\n",
    "                        if not 0 <= ci < m or not 0 <= cj < n or board[ci][cj] == '#':\n",
    "                            return True\n",
    "\n",
    "        return False\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        m, n, k = len(board), len(board[0]), len(word)\n",
    "        if n >= k:\n",
    "            for i in range(m):\n",
    "                stark, last = [], 0\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == \"#\":\n",
    "                        if j - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)): return True\n",
    "                        last, stark = j + 1, []\n",
    "                    elif board[i][j] != \" \":\n",
    "                        stark.append([j, board[i][j]])\n",
    "                if n - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)): return True\n",
    "        if m >= k:\n",
    "            for j in range(n):\n",
    "                stark, last = [], 0\n",
    "                for i in range(m):\n",
    "                    if board[i][j] == \"#\":\n",
    "                        if i - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)):   return True\n",
    "                        last, stark = i + 1, []\n",
    "                    elif board[i][j] != \" \":\n",
    "                        stark.append([i, board[i][j]])\n",
    "                if m - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        word_length = len(word)\n",
    "        # 1. 所有长度为l的连续\" \"+相邻\"#\" 水平+垂直\n",
    "        # 2. 无视英文字母，将它视为\" \"先提取出来，最后再统一判断\n",
    "        #    对比英文字母的位置和正反序word的位置，相同则ok，不相同则false\n",
    "        '''\n",
    "        将每一行每一列都拆成\"#\"区分的子串写法\n",
    "        '''\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        check = []\n",
    "        for line in board:\n",
    "            tmp = \"\".join(line).split(\"#\")\n",
    "            for each in tmp:\n",
    "                if len(each) == word_length:\n",
    "                    check.append(each)\n",
    "                    check.append(each[::-1])\n",
    "\n",
    "        for line in zip(*board):\n",
    "            tmp = \"\".join(line).split(\"#\")\n",
    "            for each in tmp:\n",
    "                if len(each) == word_length:\n",
    "                    check.append(each)\n",
    "                    check.append(each[::-1])\n",
    "        #print(check)\n",
    "        \n",
    "        def macth(word, check_list):\n",
    "            n = len(word)\n",
    "            flag = False\n",
    "            for each in check_list:\n",
    "                if each == \" \" * n:\n",
    "                    return True\n",
    "                else:\n",
    "                    for i in range(n):\n",
    "                        if each[i] != word[i] and each[i] != \" \":\n",
    "                            break\n",
    "                        if i == n - 1:\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        return macth(word, check)\n",
    "    \n",
    "    # match = lambda x, y: all(a in [' ', b] for a, b in zip(x, y))\n",
    "    # for row in chain(board, zip(*board)):\n",
    "    #     for ss in ''.join(row).split('#'):\n",
    "    #         if len(ss) == len(word) and (match(ss, word) or match(ss, word[::-1])):\n",
    "    #             return True\n",
    "    # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, grid: List[List[str]], word: str) -> bool:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        wl = len(word)\n",
    "        word_reverse = word[::-1]\n",
    "        \n",
    "            \n",
    "        for i in range(m):\n",
    "            j = 0\n",
    "            while j < n:\n",
    "                end = j\n",
    "                while end < n and grid[i][end] != '#':\n",
    "                    end += 1\n",
    "                if end - j == wl and (\n",
    "                    all(word[k] == grid[i][j + k] or grid[i][j + k] == ' ' for k in range(wl))\n",
    "                    or\n",
    "                    all(word_reverse[k] == grid[i][j + k] or grid[i][j + k] == ' ' for k in range(wl))\n",
    "                ):\n",
    "                    return True\n",
    "                j = end + 1\n",
    "        for j in range(n):\n",
    "            i = 0\n",
    "            while i < m:\n",
    "                end = i\n",
    "                while end < m and grid[end][j] != '#':\n",
    "                    end += 1\n",
    "                if end - i == wl and (\n",
    "                    all(word[k] == grid[i + k][j] or grid[i + k][j] == ' ' for k in range(wl))\n",
    "                    or\n",
    "                    all(word_reverse[k] == grid[i + k][j] or grid[i + k][j] == ' ' for k in range(wl))\n",
    "                ):\n",
    "                    return True\n",
    "                i = end + 1        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        m, n = len(board), len(board[0])\n",
    "        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # print(i, j, board[i][j])\n",
    "                if board[i][j] == word[0] or board[i][j] == ' ':\n",
    "                    # print(i, j, 1)\n",
    "                    for k in range(4):\n",
    "                        r, c = i + d[k][0], j + d[k][1]\n",
    "                        print(i, j, k, r, c)\n",
    "                        if (0<=r<m and 0<=c<n and board[r][c] == '#') or r<0 or r>=m or c<0 or c>=n:\n",
    "                            dt = (k + 2) % 4\n",
    "                            # print(i, j, k, r, c, dt)\n",
    "                            r, c = i + d[dt][0], j + d[dt][1]\n",
    "                            # print(i, j, k, r, c, dt)\n",
    "                            p = 1\n",
    "                            while  0<=r<m and 0<=c<n and p < len(word) and (board[r][c] == ' ' or board[r][c] == word[p]):\n",
    "                                r += d[dt][0]\n",
    "                                c += d[dt][1]\n",
    "                                p += 1\n",
    "                                # print(r, c, dt, p)\n",
    "                            if p == len(word):\n",
    "                                if (0<=r<m and 0<=c<n and board[r][c] == '#') or r<0 or r>=m or c<0 or c>=n:\n",
    "                                    return True\n",
    "                                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        m, n = len(board), len(board[0])\n",
    "        t = len(word)\n",
    "        # 遍历行\n",
    "        for i in range(m):\n",
    "            start = 0\n",
    "            for j in range(n+1):\n",
    "                if j < n and board[i][j] != '#': continue\n",
    "                if j - start == t: # 是否长度匹配\n",
    "                     # 正向检查\n",
    "                    if all(p1 == ' ' or p1 == p2 for p1, p2 in zip(board[i][start:j], word)): return True\n",
    "                    if all(p1 == ' ' or p1 == p2 for p1, p2 in zip(board[i][start:j], word[::-1])): return True \n",
    "                start = j + 1 #不管是否相等更新'#'\n",
    "\n",
    "        # 遍历列\n",
    "        for j in range(n):\n",
    "            start = 0\n",
    "            for i in range(m+1):\n",
    "                if i < m and board[i][j] != '#': continue\n",
    "                if i-start==t:\n",
    "                    # 正向检查  \n",
    "                    if all(p1 == ' ' or p1 == p2 for p1, p2 in zip((board[s][j] for s in range(start, i)), word)): return True    \n",
    "                    if all(p1 == ' ' or p1 == p2 for p1, p2 in zip((board[s][j] for s in range(start, i)), word[::-1])): return True\n",
    "                start = i+1 #不管是否相等更新'#'\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        def check(s: str) -> bool:\n",
    "            for i in range(wn):\n",
    "                if s[i] == ' ':\n",
    "                    continue\n",
    "                else:\n",
    "                    if s[i] != word[i]:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        \n",
    "        Row = len(board)\n",
    "        Col = len(board[0])\n",
    "        \n",
    "        wn = len(word)\n",
    "\n",
    "        #--------先按行\n",
    "        for r in range(Row):\n",
    "            c = 0\n",
    "            while c < Col:\n",
    "                if board[r][c] == '#':\n",
    "                    c += 1\n",
    "                elif board[r][c].isalpha() or board[r][c] == ' ':\n",
    "                    s = ''\n",
    "                    cur = 0\n",
    "                    while c < Col and (board[r][c].isalpha() or board[r][c] == ' '):\n",
    "                        s += board[r][c]\n",
    "                        cur += 1\n",
    "                        c += 1\n",
    "                    if cur == wn:\n",
    "                        if check(s) == True or check(s[::-1]):\n",
    "                            return True\n",
    "                    c += 1\n",
    "        #--------再按列\n",
    "        for c in range(Col):\n",
    "            r = 0\n",
    "            while r < Row:\n",
    "                if board[r][c] == '#':\n",
    "                    r += 1\n",
    "                elif board[r][c].isalpha() or board[r][c] == ' ':\n",
    "                    s = ''\n",
    "                    cur = 0\n",
    "                    while r < Row and (board[r][c].isalpha() or board[r][c] == ' '):\n",
    "                        s += board[r][c]\n",
    "                        cur += 1\n",
    "                        r += 1\n",
    "                    if cur == wn:\n",
    "                        if check(s) == True or check(s[::-1]) == True:\n",
    "                            return True\n",
    "                    r += 1\n",
    "                            \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        def check(s: str) -> bool:\n",
    "            for i in range(wn):\n",
    "                if s[i] == ' ':\n",
    "                    continue\n",
    "                else:\n",
    "                    if s[i] != word[i]:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        \n",
    "        Row = len(board)\n",
    "        Col = len(board[0])\n",
    "        \n",
    "        wn = len(word)\n",
    "\n",
    "        #--------先按行\n",
    "        for r in range(Row):\n",
    "            c = 0\n",
    "            while c < Col:\n",
    "                if board[r][c] == '#':\n",
    "                    c += 1\n",
    "                elif board[r][c].isalpha() or board[r][c] == ' ':\n",
    "                    s = ''\n",
    "                    cur = 0\n",
    "                    while c < Col and (board[r][c].isalpha() or board[r][c] == ' '):\n",
    "                        s += board[r][c]\n",
    "                        cur += 1\n",
    "                        c += 1\n",
    "                    if cur == wn:\n",
    "                        if check(s) == True or check(s[::-1]):\n",
    "                            return True\n",
    "                    c += 1\n",
    "        #--------再按列\n",
    "        for c in range(Col):\n",
    "            r = 0\n",
    "            while r < Row:\n",
    "                if board[r][c] == '#':\n",
    "                    r += 1\n",
    "                elif board[r][c].isalpha() or board[r][c] == ' ':\n",
    "                    s = ''\n",
    "                    cur = 0\n",
    "                    while r < Row and (board[r][c].isalpha() or board[r][c] == ' '):\n",
    "                        s += board[r][c]\n",
    "                        cur += 1\n",
    "                        r += 1\n",
    "                    if cur == wn:\n",
    "                        if check(s) == True or check(s[::-1]) == True:\n",
    "                            return True\n",
    "                    r += 1\n",
    "                            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        k = len(word)\n",
    "        n, m = len(board), len(board[0])\n",
    "            \n",
    "        for i in range(n):\n",
    "            st = 0\n",
    "            while st < m:\n",
    "                if board[i][st] != '#':\n",
    "                    ed = st\n",
    "                    while ed < m and board[i][ed] != '#':\n",
    "                        ed += 1\n",
    "                    if ed - st == k:\n",
    "                        flag = True\n",
    "                        for j in range(st, ed):\n",
    "                            if board[i][j] != ' ' and board[i][j] != word[j - st]: \n",
    "                                flag = False\n",
    "                                break\n",
    "                        if flag: return True\n",
    "                        flag = True\n",
    "                        for j in range(ed - 1, st - 1, -1):\n",
    "                            # if i == 2: print(board[i][j], word[ed - j - 1], ed, j)\n",
    "                            if board[i][j] != ' ' and board[i][j] != word[ed - j - 1]:\n",
    "                                flag = False\n",
    "                                break\n",
    "                        if flag: return True\n",
    "                    st = ed\n",
    "                else: st += 1\n",
    "        for i in range(m):\n",
    "            st = 0\n",
    "            while st < n:\n",
    "                if board[st][i] != '#':\n",
    "                    ed = st\n",
    "                    while ed < n and board[ed][i] != '#':\n",
    "                        ed += 1\n",
    "                    if ed - st == k:\n",
    "                        flag = True\n",
    "                        for j in range(st, ed):\n",
    "                            if board[j][i] != ' ' and board[j][i] != word[j - st]: \n",
    "                                flag = False\n",
    "                                break\n",
    "                        if flag: return True\n",
    "                        flag = True\n",
    "                        for j in range(ed - 1, st - 1, -1):\n",
    "                            if board[j][i] != ' ' and board[j][i] != word[ed - j - 1]:\n",
    "                                flag = False\n",
    "                                break\n",
    "                        if flag: return True\n",
    "                    st = ed\n",
    "                else: st += 1\n",
    "        return False\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        m, n = len(board), len(board[0])\n",
    "        k = len(word)\n",
    "\n",
    "        def check(lst):\n",
    "            if len(lst) != len(word):\n",
    "                return False\n",
    "            return all(lst[i] == \" \" or lst[i] == word[i] for i in range(k))\n",
    "\n",
    "        for i in range(m):\n",
    "            pre = 0\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"#\":\n",
    "                    if check([board[i][x] for x in range(pre, j)]):\n",
    "                        return True\n",
    "                    pre = j + 1\n",
    "            if check([board[i][x] for x in range(pre, n)]):\n",
    "                return True\n",
    "            board[i].reverse()\n",
    "            pre = 0\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"#\":\n",
    "                    if check([board[i][x] for x in range(pre, j)]):\n",
    "                        return True\n",
    "                    pre = j + 1\n",
    "            if check([board[i][x] for x in range(pre, n)]):\n",
    "                return True\n",
    "            board[i].reverse()\n",
    "            \n",
    "\n",
    "        for j in range(n):\n",
    "            lst = [board[i][j] for i in range(m)]\n",
    "            pre = 0\n",
    "            for i in range(m):\n",
    "                if lst[i] == \"#\":\n",
    "                    if check([lst[x] for x in range(pre, i)]):\n",
    "                        return True\n",
    "                    pre = i + 1\n",
    "            if check([lst[x] for x in range(pre, m)]):\n",
    "                return True\n",
    "            lst.reverse()\n",
    "            pre = 0\n",
    "            for i in range(m):\n",
    "                if lst[i] == \"#\":\n",
    "                    if check([lst[x] for x in range(pre, i)]):\n",
    "                        return True\n",
    "                    pre = i + 1\n",
    "            if check([lst[x] for x in range(pre, m)]):\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        m, n, k = len(board), len(board[0]), len(word)\n",
    "        if n >= k:\n",
    "          for i in range(m):\n",
    "              stark, last = [], 0\n",
    "              for j in range(n):\n",
    "                  if board[i][j] == \"#\":\n",
    "                      if j - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)): return True\n",
    "                      last, stark = j + 1, []\n",
    "                  elif board[i][j] != \" \":\n",
    "                      stark.append([j, board[i][j]])\n",
    "              if n - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)): return True\n",
    "        if m >= k:\n",
    "          for j in range(n):\n",
    "              stark, last = [], 0\n",
    "              for i in range(m):\n",
    "                  if board[i][j] == \"#\":\n",
    "                      if i - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)):   return True\n",
    "                      last, stark = i + 1, []\n",
    "                  elif board[i][j] != \" \":\n",
    "                      stark.append([i, board[i][j]])\n",
    "              if m - last == k and (all(word[p-last] == q for p,q in stark) or all(word[last-p-1] == q for p,q in stark)): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "      m, n = len(board), len(board[0])\n",
    "      t = len(word)\n",
    "\n",
    "      for row in board:\n",
    "        r = 0\n",
    "        while r < n:\n",
    "          if row[r] != '#':\n",
    "            l = r\n",
    "            while r < n and row[r] != '#':\n",
    "              r += 1\n",
    "            if r - l == t:\n",
    "              for i in range(l, r):\n",
    "                if row[i] != ' ' and row[i] != word[i-l]:\n",
    "                  break\n",
    "              else: return True\n",
    "              for i in range(r-1, l-1, -1):\n",
    "                if row[i] != ' ' and row[i] != word[r-i-1]:\n",
    "                  break\n",
    "              else: return True\n",
    "          else:\n",
    "            r += 1\n",
    "\n",
    "      for j in range(n):\n",
    "        r = 0\n",
    "        while r < m:\n",
    "          if board[r][j] != '#':\n",
    "            l = r\n",
    "            while r < m and board[r][j] != '#':\n",
    "              r += 1\n",
    "            if r - l == t:\n",
    "              for i in range(l, r):\n",
    "                if board[i][j] != ' ' and board[i][j] != word[i-l]:\n",
    "                  break\n",
    "              else: return True\n",
    "              for i in range(r-1, l-1, -1):\n",
    "                if board[i][j] != ' ' and board[i][j] != word[r-i-1]:\n",
    "                  break\n",
    "              else: return True\n",
    "          else:\n",
    "            r += 1\n",
    "      \n",
    "      return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        k = len(word)\n",
    "\n",
    "        def check(cur):\n",
    "            if len(cur) != len(word):\n",
    "                return False\n",
    "            return all(cur[i] == \" \" or cur[i] == word[i] for i in range(k))\n",
    "\n",
    "        def compute(lst):\n",
    "            length = len(lst)\n",
    "            pre = 0\n",
    "            for i in range(length):\n",
    "                if lst[i] == \"#\":\n",
    "                    if check([lst[x] for x in range(pre, i)]):\n",
    "                        return True\n",
    "                    pre = i + 1\n",
    "            if check([lst[x] for x in range(pre, length)]):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        for tmp in board:\n",
    "            if compute(tmp[:]) or compute(tmp[::-1]):\n",
    "                return True\n",
    "            \n",
    "        for tmp in zip(*board):\n",
    "            if compute(tmp[:]) or compute(tmp[::-1]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        def is_equal(x1,x2):\n",
    "            f1 = True\n",
    "            for i in range(len(x1)):\n",
    "                if x1[i] != ' ' and x1[i] != x2[i]:\n",
    "                    f1 = False\n",
    "                    break\n",
    "            f2 = True\n",
    "            x3 = x1[::-1]\n",
    "            for i in range(len(x3)):\n",
    "                if x3[i] != ' ' and x3[i] != x2[i]:\n",
    "                    f2 = False\n",
    "                    break\n",
    "            return f1 | f2\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(len(board)):\n",
    "            s = ''\n",
    "            for j in range(len(board[0])):\n",
    "                s += board[i][j]\n",
    "            tmp = s.split('#')\n",
    "            for k in tmp:\n",
    "                if len(k) == len(word):\n",
    "                    flag = flag | is_equal(k,word)\n",
    "        for i in range(len(board[0])):\n",
    "            s = ''\n",
    "            for j in range(len(board)):\n",
    "                s += board[j][i]\n",
    "            tmp = s.split('#')\n",
    "            for k in tmp:\n",
    "                if len(k) == len(word):\n",
    "                    flag = flag | is_equal(k,word)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        # find space with length equal to word\n",
    "        m, n = len(board), len(board[0])\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == '#':  continue\n",
    "                for d in range(4):\n",
    "                    ci, cj = i - dirs[d][0], j - dirs[d][1]\n",
    "                    if 0 <= ci < m and 0 <= cj < n and board[ci][cj] != '#': continue\n",
    "\n",
    "                    ci, cj = i, j\n",
    "                    for k in range(len(word)):\n",
    "                        if not 0 <= ci < m or not 0 <= cj < n:\n",
    "                            break\n",
    "                        if not (board[ci][cj] == word[k] or board[ci][cj] == ' '):  break\n",
    "                        ci, cj = ci + dirs[d][0], cj + dirs[d][1]\n",
    "\n",
    "                    else:\n",
    "                        if not 0 <= ci < m or not 0 <= cj < n or board[ci][cj] == '#':\n",
    "                            return True\n",
    "\n",
    "        return False\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:\n",
    "        \"\"\"\n",
    "        board = [[\"#\", \" \", \"#\"], [\" \", \" \", \"#\"], [\"#\", \"c\", \" \"]], word = \"abc\"\n",
    "        :param board:\n",
    "        :param word:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def check_valid(x, y, ways):\n",
    "            if ways == 0:\n",
    "                for i in range(len(word)):\n",
    "                    if board[x][y + i] == '#':\n",
    "                        return False\n",
    "                    if board[x][y + i] == ' ':\n",
    "                        continue\n",
    "                    if board[x][y + i] != word[i]:\n",
    "                        return False\n",
    "                if y + len(word) < len(board[0]):\n",
    "                    if board[x][y + len(word)] != '#':\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "            if ways == 2:\n",
    "                for i in range(len(word)):\n",
    "                    if board[x][y - i] == '#':\n",
    "                        return False\n",
    "                    if board[x][y - i] == ' ':\n",
    "                        continue\n",
    "                    if board[x][y - i] != word[i]:\n",
    "                        return False\n",
    "                if y - len(word) >= 0:\n",
    "                    if board[x][y - len(word)] != '#':\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "            if ways == 1:\n",
    "                for i in range(len(word)):\n",
    "                    if board[x + i][y] == '#':\n",
    "                        return False\n",
    "                    if board[x + i][y] == ' ':\n",
    "                        continue\n",
    "                    if board[x + i][y] != word[i]:\n",
    "                        return False\n",
    "                if x + len(word) < len(board):\n",
    "                    if board[x + len(word)][y] != '#':\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "            if ways == 3:\n",
    "                for i in range(len(word)):\n",
    "                    if board[x - i][y] == '#':\n",
    "                        return False\n",
    "                    if board[x - i][y] == ' ':\n",
    "                        continue\n",
    "                    if board[x - i][y] != word[i]:\n",
    "                        return False\n",
    "                if x - len(word) >= 0:\n",
    "                    if board[x - len(word)][y] != '#':\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == '#':\n",
    "                    if len(board[0]) - j - 1 >= len(word):\n",
    "                        res = check_valid(i, j + 1, 0)\n",
    "                        if res:\n",
    "                            return True\n",
    "\n",
    "                    if j - 1 >= len(word)-1:\n",
    "                        res = check_valid(i, j - 1, 2)\n",
    "                        if res:\n",
    "                            return True\n",
    "\n",
    "                    if len(board) - i - 1 >= len(word):\n",
    "                        res = check_valid(i + 1, j, 1)\n",
    "                        if res:\n",
    "                            return True\n",
    "\n",
    "                    if i -1 >= len(word)-1:\n",
    "                        res = check_valid(i - 1, j, 3)\n",
    "                        if res:\n",
    "                            return True\n",
    "\n",
    "        # four board\n",
    "        for i in range(len(board[0])):\n",
    "            if board[0][i] == ' ' or board[0][i] == word[0]:\n",
    "                if len(board) >= len(word):\n",
    "                    res = check_valid(0, i, 1)\n",
    "                    if res:\n",
    "                        return True\n",
    "\n",
    "        lastrow = len(board) -1\n",
    "        for i in range(len(board[0])):\n",
    "            if board[lastrow][i] == ' ' or board[lastrow][i]  == word[0]:\n",
    "                if len(board) >= len(word):\n",
    "                    res = check_valid(lastrow, i, 3)\n",
    "                    if res:\n",
    "                        return True\n",
    "\n",
    "        lastline = len(board[0]) - 1\n",
    "        for i in range(len(board)):\n",
    "            if board[i][0] == ' ' or board[i][0] == word[0]:\n",
    "                if len(board[0]) >= len(word):\n",
    "                    res = check_valid(i, 0, 0)\n",
    "                    if res:\n",
    "                        return True\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            if board[i][lastline] == ' ' or board[i][lastline] == word[0]:\n",
    "                if len(board[0]) >= len(word):\n",
    "                    res = check_valid(i, lastline, 2)\n",
    "                    if res:\n",
    "                        return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
